package comLibs.findingPath
{
	/**
	 * 
	 * @author zihol.luo
	 * 
	 */	
	public class Ami
	{
		private var _open:Array;
		private var _closed:Array;
		private var _grid:Grid;
		private var _startNode:Node;
		private var _endNode:Node;
		private var _path:Array;
//		private var _heuristic:Function = manhattan;
		private var _heuristic:Function = euclidian;
//		private var _heuristic:Function = diagonal;
		private var _straightCost:Number  = 1;
		private var _diagCost:Number = Math.SQRT2;
		public function Ami()
		{
		}
		public function findPath(grid:Grid):Boolean
		{
			_grid = grid;
			_open = new Array();
			_closed = new Array();
			_startNode = _grid.startNode;
			_endNode = _grid.endNode;
			_startNode.g = 0;
			_startNode.h = _heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;
			return search();
		}
		private function search():Boolean
		{
			var node:Node = _startNode;
			while(node!=_endNode)
			{
				var startX:int = Math.max(0,node.x-1);
				var startY:int = Math.max(0,node.y-1);
				var endX:int = Math.min(_grid.numCols-1,node.x +1);
				var endY:int = Math.min(_grid.numRows-1,node.y +1);
				for(var i:int=startX;i<=endX;i++) // 此for循环用以变量临近八个节点 求得他们的从当前节点到终点的代价
				{
					for(var j:int=startY;j<=endY;j++)
					{
						var test:Node = _grid.getNode(i,j);
						if(
							test==node
							|| !test.walkable
							|| !_grid.getNode(node.x,test.y).walkable
							|| !_grid.getNode(test.x,node.y).walkable
						  )// 不能通过 或是当前节点则跳过此次循环继续
						{
							continue;
						}
						var cost:Number = _straightCost;
						if(!((node.x==test.x)||(node.y==test.y))) // 如果不是正上下左右的临近点
						{
							cost = _diagCost;
						}
						var g:Number = node.g + cost*test.costMultipler;
						var h:Number = _heuristic(test);
						var f:Number = g+h; // 算出test 点的代价
						if(isOpen(test) || isClose(test)) // 如果不再待考察表或不在已考察表里
						{
							if(test.f>f) // 比较经过时之前当前节点与现在当前节点的代价多少，如果以前代价大就不动
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}else{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							_open.push(test);
						}
					} // end for
				}// end for
				for(var o:int=0;o<_open.length;o++)
				{
					
				}
				_closed.push(node);
				if(_open.length==0)
				{
					trace('path not found');
					return false;
				}
				_open.sortOn('f',Array.NUMERIC); // 排序
				node = _open.shift() as Node; // 用代价最小的开始作为当前点,弹出不留在待考察表中,下次轮到别的节点
			}
			buildPath();
			return true;
		}// end function
		private function isOpen(node:Node):Boolean
		{
			for(var i:int=0;i<_open.length;i++)
			{
				if(_open[i]==node)
				{
					return true;
				}
			}
			return false;
		}// end func
		private function isClose(node:Node):Boolean
		{
			for(var i:int=0;i<_closed.length;i++)
			{
				if(_closed[i]==node)
				{
					return true;
				}
			}
			return false;
		}// end func
		private function buildPath():void
		{
			_path = new Array();
			var node:Node = _endNode;
			_path.push(node);
			while(node!=_startNode)
			{
				node = node.parent;
				_path.push(node);
			}
		}// end func
		private function manhattan(node:Node):Number
		{
			return Math.abs(node.x - _endNode.x)*_straightCost+Math.abs(node.y-_endNode.y)*_straightCost;
		}
		private function euclidian(node:Node):Number
		{
			var dx:Number = node.x - _endNode.x;
			var dy:Number = node.y - _endNode.y;
			return Math.sqrt(dx*dx+dy*dy);
		}
		private function diagonal(node:Node):Number
		{
			var dx:Number = Math.abs(node.x - _endNode.x);
			var dy:Number = Math.abs(node.y - _endNode.y);
			var diag:Number = Math.min(dx,dy);
			return diag*_diagCost+_straightCost*(dx+dy-2*diag);
		}// end function
        public function get visited():Array
        {
            return _closed.concat(_open);
        }
        public function get path():Array
        {
            return _path;
        }
	}
}